package com.aqie.arithmetic.datastructure;

import java.util.Iterator;

/**
 * 基于链表实现队列
 */
public class LinkedListQueue<T> implements Iterable<T> {
    // 最早添加的节点
    private Node first;
    // 最近添加的节点
    private Node last;
    // 队列中元素数量
    private int N;

    @Override
    public Iterator<T> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<T>{
        private Node current = first;
        public boolean hasNext(){
            return current != null;
        }
        public void remove(){}

        public T next(){
            T item = current.item;
            current = current.next;
            return item;
        }

    }

    private class Node{
        // 定义结点的嵌套类
        T item;
        Node next;
    }

    public boolean isEmpty(){
        return first == null;
    }

    public int size(){
        return N;
    }

    public void enqueue(T item){
        // 向表尾添加元素
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldlast.next = last;
        N++;
    }

    public T dequeue(){
        // 从表头删除元素
        T item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        N--;
        return item;
    }
}
